#leetcode题目41：缺失的第一个正数
#难度：困难
#时间复杂度：O(n)
#空间复杂度：O(1)
#方法：原地哈希

#特别要求：使用常数空间解决这个问题,复杂度只能为O(n)

from typing import List
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n=len(nums)
        for i in range(n):
            if nums[i]<=0:
                nums[i]=n+1
        for i in range(n):
            num=abs(nums[i])
            if num<=n:
                nums[num-1]=-abs(nums[num-1])
        for i in range(n):
            if nums[i]>0:
                return i+1
        return n+1



#测试数据
nums=[1,2,0]
#预期输出：3
solution=Solution()
print(solution.firstMissingPositive(nums))

nums=[3,4,-1,1]
#预期输出：2
solution=Solution()
print(solution.firstMissingPositive(nums))

nums=[7,8,9,11,12]
#预期输出：1
solution=Solution()
print(solution.firstMissingPositive(nums))


